package util;


import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;


public class LinkedList<A> implements List<A> {

	protected class Node {
		A		data;
		Node	prev, next;

		public Node() {
			this(null,null,null);
		}
		
		public Node(A data)	{
			this.data = data;
			this.next = null;
			this.prev = null;
		}
		
		public Node(Node prev, A data,Node next) {
			this.data = data;
			this.prev = prev;
			this.next = next;
		}
	}

	public class FastLinkedListIterator implements Iterator<A> {
	    
		Node current;

		/**
	     * Construct the list iterator
	     * @param head any node in the linked list.
	     */
	    FastLinkedListIterator( Node head ) {
	        current = head;
	    }
	    
	    /**
	     * Test if the current position is a valid position in the list.
	     * @return true if the current position is valid.
	     */
	    public boolean isValid( ) {
	        return current != null;
	    }
	    
	    /**
	     * Advance the current position to the next node in the list.
	     * If the current position is null, then do nothing.
	     */
	    
	    public void advance( ) {
	    	throw new UnsupportedOperationException();
	        //if( isValid() )
	       //     current = current.next;
	    }
	
	    /**
	     * Retreat the current position to the node before in the list.
	     * If the current position is null, then do nothing.
	     */
	    
	    public void Retreat( ) {
	    	throw new UnsupportedOperationException();
	        //if( isValid() )
	        //    current = current.prev;
	    }
	    
	    public boolean hasBack() {
	    	throw new UnsupportedOperationException();
			//return current.prev != null ;
		}

		public boolean hasNext() {
			return current != null ;
		}

		public A back() {
			throw new UnsupportedOperationException();
			//current = current.prev;
			//return current.data;
		}
		
		public A next() {
			A temp = current.data;
			current = current.next;
			return temp;
			//return current.data;
		}
		
		public void remove() {
			throw new UnsupportedOperationException();
		}
	}

	/**
	 * head and tail of the list
	 */
	protected Node	head,tail;
	protected int   size;

	public LinkedList() {
		head = tail = null;
		size = 0;
	}

	public LinkedList(A o) {
		head = tail = new Node(o);
		size = 1;
	}

	/**
     * Insert at the end
     * @param o the item to insert.
     * 
     * */
	public boolean add(A o) {
		if (tail == null) {
			assert (head == null);
			head = tail = new Node(o);
		}
		else {
			assert (head != null);
			Node node = new Node(o);
			node.prev = tail;
			tail.next = node;
			tail = node;
		}
		size++;
		return true;
	}

	// unimplemented
	public void add(int index, A element) {
		throw new UnsupportedOperationException();
	}

	/**
	 * appends another list to myself
	 * @param list the list to append
	 */
	public void addList(LinkedList<A> list)
	{
		assert(list != null);
		
		if (tail != null) {
			tail.next = list.head;
		}
		else {
			head = list.head;
		}
		
		if (list.head != null) {
			list.head.prev = tail;
			tail = list.tail;
		}
		
		size += list.size;
	}

	public boolean addAll(Collection<? extends A> c) {
		assert(c != null);
		
		if (c instanceof LinkedList) {
			addList((LinkedList<A>)c);
			return true;
		}
		else {
			throw new UnsupportedOperationException("appends only FastLists");
		}
		//return false;
	}

	// unimplemented
	public boolean addAll(int index, Collection<? extends A> c) {
		throw new UnsupportedOperationException();
	}

	public void clear() {
		head = null;
		tail = null;
	}

	// unimplemented
	public boolean contains(Object o) {
		throw new UnsupportedOperationException();
	}

	// unimplemented
	public boolean containsAll(Collection<?> c) {
		throw new UnsupportedOperationException();
	}

	// unimplemented
	public A get(int index) {
		throw new UnsupportedOperationException();
	}

	// unimplemented
	public int indexOf(Object o) {
		throw new UnsupportedOperationException();
	}

	public boolean isEmpty() {
		if (size == 0) 
			return true; 
		else
			return false;
	}

	public Iterator<A> iterator() {
		return new FastLinkedListIterator(head);
	}

	// unimplemented
	public int lastIndexOf(Object o) {
		throw new UnsupportedOperationException();
	}

	public ListIterator<A> listIterator() {
		return (ListIterator<A>) new FastLinkedListIterator(head);
	}

	// unimplemented
	public ListIterator<A> listIterator(int index) {
		throw new UnsupportedOperationException();
	}

	// unimplemented
	public boolean remove(Object o) {
		throw new UnsupportedOperationException();
	}

	// unimplemented
	public A remove(int index) {
		throw new UnsupportedOperationException();
	}

	// unimplemented
	public boolean removeAll(Collection<?> c) {
		throw new UnsupportedOperationException();
	}

	// unimplemented
	public boolean retainAll(Collection<?> c) {
		throw new UnsupportedOperationException();
	}

	// unimplemented
	public A set(int index, A element) {
		throw new UnsupportedOperationException();
	}

	public int size() {
		return size;
	}

	// unimplemented
	public List<A> subList(int fromIndex, int toIndex) {
		throw new UnsupportedOperationException();
	}

	public Object[] toArray() {
		List<Object> temp = new ArrayList<Object>();
		
		FastLinkedListIterator it = new FastLinkedListIterator(head);
		while (it.hasNext()) {
			temp.add(it.next());
		}
		
		Object[] arr = new Object[temp.size()];
		temp.toArray(arr);
		return arr;
	}

	//	 unimplemented
	public <T> T[] toArray(T[] a) {
		throw new UnsupportedOperationException();
	}
	
}